/*
 * File:   FreeList.cpp
 * Author: chris
 *
 * Created on January 25, 2009, 8:39 PM
 */

#include <iostream>
using namespace std;
#include "BlockLinkedList.h"
#include "BlockGroup.h"
#include "BlockGroupException.h"
#include "MasterBlock.h"
#include "Util.h"
#include <stdlib.h>
#include "BlockException.h"
#include "FreeListException.h"
#include "FreeList.h"


FreeList::FreeList(Disk *disk, bool createFreeList) {
    m_closed = false;
	m_disk = disk;
	
    // don't take off four here because the BlockLinkedList::GetBlockSize does that.
    m_blockSize = m_disk->blockSize();
	
    // Need to read block 0 and get the free list start block number from there.
    if (createFreeList) {
        m_numberOfBlocks = m_disk->numberOfBlocks() - 1;
        Reformat();
    } else {
        // Get the start, end block number, and number of blocks from block 0
        FSBlock *blk = new FSBlock(0, m_disk);
		
        // The start block number is stored as the "next pointer", i.e., the first four bytes
        // of the block data.
        m_startBlockNumber = blk->GetInt(MasterBlock::FREELIST_START_BLOCK_NUMBER);
		
		// Check for error: If the freelist is empty, 
		// it is possible that the startblock number
		// and end block number can be 0.
        if (((int) m_startBlockNumber < 0) || 
                (m_startBlockNumber >= m_disk->numberOfBlocks()))  {
            printf("BlockGroup: ERROR: startBlockNumber: %d!\n", m_startBlockNumber);
            delete blk;
            throw BlockGroupException();
        }
		
        // The second four bytes of the block data are the end block number
        m_endBlockNumber = blk->GetInt(MasterBlock::FREELIST_END_BLOCK_NUMBER);
        if (((int) m_endBlockNumber < 0) || (m_endBlockNumber >= m_disk->numberOfBlocks())) {
			printf("BlockGroup: ERROR: m_endBlockNumber: %d!\n", m_endBlockNumber);
            delete blk;
            throw BlockGroupException();
        }
		
        // The third four bytes of the block data are the number of blocks
        m_numberOfBlocks = blk->GetInt(MasterBlock::FREELIST_NUMBER_BLOCKS);
		if (((int) m_numberOfBlocks < 0) || (m_numberOfBlocks >= m_disk->numberOfBlocks()))  {
            printf("BlockGroup: ERROR: m_numberOfBlocks: %d!\n", m_numberOfBlocks);
            delete blk;
            throw BlockGroupException();
        }
		
        Rewind();
		
        printf("FreeList: startBlockNumber= %d\n", m_startBlockNumber);
        printf("FreeList: endBlockNumber= %d\n", m_endBlockNumber);
        printf("FreeList: numberOfBlocks= %d\n", m_numberOfBlocks);
        delete blk;
    }
}


bool FreeList::Close()  {
    m_closed = true;


    // Need to first read block 0 from the file
    FSBlock *blk = new FSBlock(0, m_disk);
	
    //printf("Here2"); System.out.flush();
	
    // We need to put the start block number of this block group as the first four bytes
    // of the m_buffer of this block; SetNextPointer will do this.
    blk->SetInt(m_startBlockNumber, MasterBlock::FREELIST_START_BLOCK_NUMBER);
	
    // We need to put the end block number of this block group as the second four bytes
    // of the m_buffer of this block.
    blk->SetInt(m_endBlockNumber, MasterBlock::FREELIST_END_BLOCK_NUMBER);
	
    // Finally, store the number of blocks in the freelist in the masterblock
    blk->SetInt(m_numberOfBlocks, MasterBlock::FREELIST_NUMBER_BLOCKS);
	
    // Write the modified block to the Disk
    if (!blk->Write(m_disk)) {
        delete blk;
        return false;
    }
	
    //printf("Here3"); System.out.flush();
    printf("FreeList.Close: SUCCESS: Wrote block 0 (masterblock).\n");
    printf("FreeList.Close: SUCCESS: starting block of free list= %d\n",
		   m_startBlockNumber);
    printf("FreeList.Close: SUCCESS: ending block of free list= %d\n",
		   m_endBlockNumber);
    printf("FreeList.Close: SUCCESS: number of blocks in the free list= %d\n",
		   m_numberOfBlocks);
	
    delete blk;
	
    return true;
}


void FreeList::Return(BlockLinkedList *bll) {
    if (m_closed) {
        printf("FreeList.Return: ERROR: FreeList is already closed\n");
        throw FreeListException();
    }

    FSBlock *blk;

	
    for (;;) {
	    // Stop freeing up the blocks of this BlockLinkedList when it has no more blocks.
        if (bll->GetNumberOfBlocks() == 0) break;
		
        printf("FreeList.Return: Unlinking block\n");
		
        // unlink the first block in the bll BlockLinkedList
        blk = bll->UnlinkBlock();
		
        // Return this block to the free list.
        AddBlock(blk);
		
        delete blk;
    }
}


BlockGroup *FreeList::CreateNew() {
    if (m_closed) {
        printf("FreeList.CreateNew: ERROR: FreeList is already closed\n");
        throw FreeListException();
    }

	printf("FreeList.CreateNew: Starting\n"); fflush(stdout);
	
	
    BlockGroup *group = new BlockGroup((BlockLinkedList *) this);
	printf("FreeList.CreateNew: after BlockGroup constructor\n"); fflush(stdout);
    group->SetFreeList(this); // the Free List of our new BlockGroup is now set properly.
    FSBlock *blk = NULL;
	
	
    blk = UnlinkBlock();
    if (blk == NULL) {
		printf("FreeList.CreateNew: ERROR: FreeList is empty!\n"); fflush(stdout);
        delete group;
        return NULL;
    }
	
    blk->ClearBuffer();
	
    group->m_startBlockNumber = blk->GetBlockNumber(); 
    group->m_endBlockNumber = blk->GetBlockNumber();
    blk->SetInt(0, 0);
	
    if (! blk->Write(m_disk)) {
        delete blk;
        delete group;
        printf("FreeList.CreateNew: Error calling Write\n");
        return NULL;
    }
	
    group->m_numberOfBlocks = 1;
    delete blk;
    
    return group;
}

#define DEVICE_NAME_LENGTH 100

void FreeList::Test(bool menu, const char *filename, int StartBlockNumber[]) {
    int cmd = 0;
    Disk *disk = NULL;
    //int blockNumber = 0;
    //int byteToWrite;
    FreeList *mother = NULL;
    BlockGroup *bg1 = NULL;
    bool physicalDevice = false;
    unsigned int blockSize = Disk::DEFAULT_BLOCK_SIZE;
    char deviceName[DEVICE_NAME_LENGTH] = "disk1";
    unsigned long numberOfBlocks = DEFAULT_NUMBER_OF_BLOCKS;
    
    // This is intended for a web-based testing program, so it only makes sense to use a simulated
    // disk in a file here.
    if (! menu) {
        DebugDisk(filename, StartBlockNumber);
        exit(1);
    }
	
    for (;;) {
        printf("\nmain: Enter command:\n");
        printf("   0) Exit program\n");
        printf("   1) use physical device (default is to use simulated file system in a file)\n");
        printf("   2) create and format FreeList\n");
        printf("   3) open and don't format FreeList\n");
        printf("   4) close FreeList\n");
        printf("   5) output block numbers in FreeList\n");
		
        printf("   6) create BlockGroup bg1\n");
        printf("   7) return BlockGroup bg1 to FreeList\n");
        printf("   8) add block to BlockGroup bg1\n");
        printf("   9) output block numbers of BlockGroup bg1\n");
        printf("   10) re-open BlockGroup bg1\n");
        printf("Enter command: ");
        ScanfTest("%d", &cmd);
		
        switch (cmd) {
            case 0:
                return;
				
            case 1:
                printf("Enter name of physical disk device: ");
                cin.getline(deviceName, DEVICE_NAME_LENGTH);
                physicalDevice = true;
                Disk::GetSizes(deviceName, numberOfBlocks, blockSize);
                break;
				
            case 2: // create and format freelist
                disk = new Disk(deviceName, numberOfBlocks, blockSize, physicalDevice);
                mother = new FreeList(disk, true);
                break;
				
            case 3: 
                disk = new Disk(deviceName, numberOfBlocks, blockSize, physicalDevice);
                mother = new FreeList(disk, false);
                break;
				
            case 4:
                mother->Close();
                break;
				
            case 5:
                mother->Output();
                break;
				
            case 6:
                bg1 = mother->CreateNew();
                break;
				
            case 7:
                mother->Return((BlockLinkedList *) bg1);
                break;
				
            case 8:
                bg1->AddBlock();
                break;
				
            case 9:
                bg1->Output();
                break;
				
            case 10:
			{
				int startBlock, endBlock, numberOfBlocks;
				printf("Enter start block: ");
				ScanfTest("%d", &startBlock);
				printf("Enter end block: ");
				ScanfTest("%d", &endBlock);
				printf("Enter number of blocks: ");
				ScanfTest("%d", &numberOfBlocks);
				bg1 = new BlockGroup(startBlock, endBlock, numberOfBlocks, mother);
			}
                break;
				
            default:
                printf("main: Bad command!\n");
                break;
        } // end switch
    } // end for
} // end Test()


void FreeList::DebugDisk(const char *filename, int StartBlockNumbers[]) {
	FreeList *mother = NULL;

    printf("FreeList::DEFAULT_NUMBER_OF_BLOCKS= %d\n", FreeList::DEFAULT_NUMBER_OF_BLOCKS);

	Disk *disk = new Disk(filename, 
	        FreeList::DEFAULT_NUMBER_OF_BLOCKS, Disk::DEFAULT_BLOCK_SIZE, 
		false /* not a physical device */);
	mother = new FreeList(disk, false);
	
	// Print out the contents of the master block with respect to the free list
	// These will be present as data members of the free list as we just read the 
	// master block.
	/*
	 printf("start block number: %d\n", mother->m_startBlockNumber);
	 printf("end block number: %d\n", mother->m_endBlockNumber);
	 printf("number of blocks: %d\n", mother->m_numberOfBlocks);
	 */
	
    printf("\n");

	for (int index=0; StartBlockNumbers[index] != 0; index++) {
		// Iterate over the blocks of a block group, from a StartBlockNumber
		// to the end of the BlockGroup, printing out the block numbers
        printf("Blocks of BlockGroup:");
        TestBlockGroup(StartBlockNumbers[index], mother);
        printf("\n");
	}

    Check(mother);
}


int FreeList::TestBlockGroup(int startBlockNumber, FreeList *mother) {
    int last = 0;

	// Iterate over the blocks of a block group, from a StartBlockNumber
	// to the end of the BlockGroup, printing out the block numbers
	FSBlock *blk = new FSBlock(startBlockNumber, mother->m_disk);
	printf("%d", startBlockNumber);
	
	for (;;) {
		int nextBlock = blk->GetInt(0); // get the pointer to the next block
		if (0 == nextBlock) {
			break; // end of BlockGroup
		}
        
		// Error checking
		if ((nextBlock < 0) || (nextBlock >= DEFAULT_NUMBER_OF_BLOCKS)) {
		    printf("ERROR: nextBlock number is out of range (= %d)\n", nextBlock);
		    exit(1);
		}
		
		printf(", %d", nextBlock);
		delete blk;
		blk = new FSBlock(nextBlock, mother->m_disk);
	}
    last = blk->GetBlockNumber();
	delete blk;
	printf("\n");
    return last;
}


void FreeList::Check(FreeList *mother) {
    FSBlock *blk;

	printf("FreeList Information:\n");		
	// Print out the block numbers of the blocks in the FreeList
	mother->Output();

    // This should not fail
    try {
        blk = new FSBlock(DEFAULT_NUMBER_OF_BLOCKS-1, mother->m_disk);
        delete blk;
    } catch (BlockException e) {
        printf("ERROR: Disk does not have %d blocks!\n", DEFAULT_NUMBER_OF_BLOCKS);
    }

    // Make sure that the disk only has 100 blocks
    if (mother->m_disk->CheckBlock(DEFAULT_NUMBER_OF_BLOCKS)) {
        // CheckBlock only returns true when the block is valid
        printf("FreeList.Check: ERROR: Disk appears to have more than 100 blocks total\n");
        exit(1);
    }
    
    /*
    The following doesn't work because of the error handling within FSBlock.

    FSBlock::Debug(false);

    bool correctSize = false;
    try {
        blk = new FSBlock(DEFAULT_NUMBER_OF_BLOCKS, mother->m_disk);
        delete blk;
    } catch (BlockException e) {
        // we get to here only if disk did not have more than 100 blocks (block number 100 is actually
        // block number 101 since we start at 0). i.e., we get to here if we have the correct number
        // of blocks on the disk.
        correctSize = true;
    }
    
    FSBlock::Debug(true);
    
    if (! correctSize) {
        printf("ERROR: Disk has more than %d blocks!\n", DEFAULT_NUMBER_OF_BLOCKS);
        exit(1);
    }
    */
    
    // Could we do some more testing? E.g., go through the links in the Disk and
    // make sure each block occurs in at most one list.
    
    // Each element is going to contain a count of the number of references
    // to this block. ie., blockNumber[i] = the number of times that block is referenced
    // from a block. For block numbers, i, between 1 and DEFAULT_NUMBER_OF_BLOCKS-1, this should 
    // be exactly one. That is, the block should either be on the free list or it should
    // be on another linked list.
    int blockNumbers[DEFAULT_NUMBER_OF_BLOCKS];
    
    // Initialize blockNumbers list
    for (int i=1; i < DEFAULT_NUMBER_OF_BLOCKS; i++) {
        blockNumbers[i] = 0;
    }
	
	// the pointer to the start of the free list in the master block counts
	// as a reference to a block (the pointer to the last block doesn't since
	// the last block will be referenced from the free list itself).
	blockNumbers[mother->m_startBlockNumber]++;
    
    // Now go through the disk
    printf("DEFAULT_NUMBER_OF_BLOCKS= %d\n", DEFAULT_NUMBER_OF_BLOCKS);
    for (int i=1; i < DEFAULT_NUMBER_OF_BLOCKS; i++) {
        blk = new FSBlock(i, mother->m_disk);
        int nextBlock = blk->GetInt(0);
        delete blk;
        if ((nextBlock < 0) || (nextBlock >= DEFAULT_NUMBER_OF_BLOCKS)) {
            printf("ERROR: Block number %d refers to an incorrect block number (%d)\n", i, nextBlock);
        } else if (nextBlock != 0) {
            blockNumbers[nextBlock]++;
        }
    }
    
    for (int i=1; i < DEFAULT_NUMBER_OF_BLOCKS; i++) {
        if (blockNumbers[i] > 1) {
            printf("ERROR: Block number %d appears on more than one (%d) list\n", 
				   i, blockNumbers[i]);
        }
    }
}


bool FreeList::Reformat() {
    printf("FreeList.Reformat: Creating free list for Disk\n");
    printf("FreeList.Reformat: Disk will have %lu blocks\n", m_disk->numberOfBlocks());
    
    m_startBlockNumber = 1;
    // new Block; not written to disk yet
    FSBlock blk(m_disk->blockSize());
	
    // Use as the last block number for the free list one less than the number of blocks
    // on the disk, because the free list starts at block 1 on the disk, and ends
    // at the last block on the disk.
    m_endBlockNumber = m_disk->numberOfBlocks() - 1;
	
    // Iterate over the blocks of the Disk. Need to write out pointer values for each one.
    // Block 1 will have a pointer to block 2,
    // block 2 will have a pointer to block 3,
    // ...
    // the last block will have a pointer 0. i.e., 0 is an invalid block number.
	
    // Use as the upper bound the number of blocks on the disk, because we
    // are initializing all blocks on the disk.
    for (unsigned int i=m_startBlockNumber; i < m_disk->numberOfBlocks(); i++) {
        int pointerNum;
		
        if (i == m_endBlockNumber) {
            pointerNum = 0;
        } else {
            pointerNum = i+1;
        }
		
        blk.SetBlockNumber(i);
        blk.SetInt(pointerNum, 0);
        if (! blk.Write(m_disk)) {
            return false;
        }
    }
	
    return true;
}


